home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / deltablu / readme.txt < prev    next >
Text File  |  1980-01-15  |  4KB  |  84 lines
  1. This directory contains the source code for an implementation of the
  2. DeltaBlue incremental dataflow constraint solver written in portable C.
  3.  
  4. The files are:
  5.   List.h,.c -- a simple ordered list abstract data type
  6.   Constraints.h,.c -- basic constraint and variable definitions
  7.   DeltaBlue.h,.c -- the DeltaBlue algorithm
  8.   UsefulConstraints.h,.c -- functions to build some useful constraints
  9.   TestDeltaBlue.c -- DeltaBlue benchmark program
  10.   DBBench.c -- an alternative DeltaBlue benchmark program
  11.   Readme.txt -- this file
  12.  
  13. The List abstract data type supports variable-sized, ordered collections
  14. of objects. Lists are used to represent plans, sets of constraints, and
  15. are used in various internal data structures.
  16.  
  17. Constraints are applied to Variable objects. New variables are created by
  18. calling Variable_Create() or Variable_CreateConstant(). The latter is a
  19. convenient way to generate read-only constants for use in equations such as
  20. a Fahrenheit-Celsius converter. For debugging purposes, variables may be
  21. given names up to 9 characters long. These names are used only when
  22. printing the variable and need not be unique.
  23.  
  24. The value field of a Variable may be examined by the client program at
  25. any time. In order to ensure that constraints are enforced, however, the
  26. client program must add edit constraints to any variables it wishes to
  27. change and must only proceed if this edit constraint can be satisfied.
  28. There is an example of how to do this in TestDeltaBlue.c.
  29.  
  30. Each kind of constraint has a corresponding creation procedure in
  31. UsefulConstraints.c. For example, an Add constraint is created and
  32. bound to the variables x, y and z by writing:
  33.  
  34.     AddC(x, y, z, S_required)
  35.  
  36. This creates an instance of an Add constraint, binds it to the given
  37. variables, and installs it with a strength of "required". It may be
  38. destroyed later by calling DestroyConstraint().
  39.  
  40. The behavior of a constraint is defined by a case statement on the value
  41. of "constraint->whichMethod". If the value of whichMethod is NO_METHOD,
  42. the constraint execution procedure does nothing. Otherwise, one of the
  43. arms of the case statement will be executed, causing one of the constrained
  44. variables to be modified to enforce the constraint. The programer must
  45. supply an "execute" procedure for each kind of constraint. The default
  46. "execute" procedure simply does nothing. The programmer must also specify
  47. the number of methods (arms of the case statement) and which variable is
  48. changed by each method. There are several examples of how to define new
  49. kinds of constraints in UsefulConstraints.c.
  50.  
  51. To enforce the constraints, a resatisfaction plan is obtained from
  52. the constraint graph. There are several ways to do this. The plan can
  53. be constructed starting from a set of edit or other input constraints.
  54. Alternatively, DeltaBlue's internal list of variables can be used as
  55. the starting point for constructing the plan. The latter is sometimes
  56. more convenient but takes time proportional to the number of variables
  57. in the system. Once a plan has been obtained, it may be executed repeatedly
  58. to propagate changes through the constraint graph. This technique can be
  59. used to provide continuous feedback in a user interface when, for example,
  60. the user drags a graphic object with the mouse.
  61.  
  62. In this implementation, plans contain pointers to actual constraints
  63. and each constraint keeps track of the method to execute. This means
  64. that, in this implementation, a plan cannot be used once the constraint
  65. graph has changed (because the method each constraint executes may have
  66. changed as a side effect of constraint satisfaction). Thus, one cannot
  67. cache plans for later re-use. This could be easily changed by recording
  68. the value of "whichMethod" along with each constraint in the plan.
  69.  
  70. The performance of DeltaBlue is good enough to handle thousands of
  71. constraints on a Mac II and tens of thousands of constraints on a
  72. DECStation. The test program includes a number of benchmarks. Some C
  73. libraries have poor implementations of "malloc" which can slow down the
  74. algorithm considerably. 
  75.  
  76. The entire DeltaBlue algorithm as described in the DeltaBlue tech report
  77. is implemented in "DeltaBlue.c". See the tech report for a description and
  78. comments. For the most part, this implementation is a direct transcription
  79. of the pseudocode in the tech report into C.
  80.  
  81.     John Maloney
  82.     April 2, 1991
  83.  
  84.